package TenkindsOfAlgorithm.dynamicProgramming;

import java.util.Arrays;

public class Package01 {
    public static void main(String[] args) {
        int[] weight = {2,3,4,5}; // 重量
        int[] value = {3,4,5,6};  // 价值
        fun(weight, value, 9);
        int[] weight2 = {1,3,5}; // 重量
        int[] value2 = {1,3,6};  // 价值
        //fun(weight2, value2, 8);
        System.out.println(fun_rec(weight, value, 3, 9));  //11
    }
    // 计数器
    private static int counts=0;
    /**
     * 先来一个递归版本的 i 表示第几个
     */
    public static int fun_rec(int []weight,int []value,int i,int sum){
        // 走到第0个物品  结束
        if(i==-1){
            return 0;
        }
        // 背包装完了
        if(sum==0){
            return 0;
        }
        if(weight[i]>sum){
            // 装不下 最优解为装上个
            return fun_rec(weight,value,i-1,sum);
        } else {
            // 不装
            int A = fun_rec(weight,value,i-1,sum);
            // 装
            int B = fun_rec(weight,value,i-1,sum-weight[i])+value[i];
            return Math.max(A,B);
        }
    }
    /**
     * 先来一个非递归版本的 二维数组存储了装了哪些值，并且解决了递归重叠值的问题
     */
    public static void fun(int[] weight, int[] value, int sum) {
        int[][] opt = new int[value.length + 1][sum + 1];
        for (int i = 0; i < opt[0].length; i++) {
            opt[0][i] = 0;
        }
        for (int i = 0; i < opt.length; i++) {
            opt[i][0] = 0;
        }
        int A;
        int B;
        // 以上可以不写 但有这个过程、
        for (int i = 1; i < opt.length; i++) {
            for (int j = 1; j < opt[0].length; j++) {
                // 背包装不下
                if (weight[i - 1] > j) { // 因为我们for循环是从1开始的，但1在数组中表示第二个element
                    opt[i][j] = opt[i - 1][j];
                } else {
                    // 不装
                    A = opt[i - 1][j];
                    // 理解value[i-1] 与 weight[i-1] 还是数组原因
                    B = value[i - 1] + opt[i - 1][j - weight[i - 1]];
                    opt[i][j] = Math.max(A, B);
                }
            }
        }
        for (int[] ints : opt) {
            System.out.println(Arrays.toString(ints));
        }
        // puls 我们需要将放入背包的数据取出来
        int i = opt.length - 1;
        int j = opt[0].length - 1;
        while (i >= 1 && j >= 1) {
            if (opt[i][j] > opt[i - 1][j]) {
                System.out.println("放入了价值为" + value[i - 1] + "的元素");
                // 因为放入了东西 容量变小了 故i-1个元素最大容量减去相应的质量
                j = opt[i][j] - value[i - 1] ;
            }else {
                // j 不变
            }
            i = i - 1;
        }
    }
}
